import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;

public class Greedy {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> hashMap=new HashMap<>();

        HashSet<String> hashSet=new HashSet<>();
        hashSet.add("杭州");
        hashSet.add("北京");
        hashSet.add("上海");
        hashSet.add("天津");

        HashSet<String> hashSet1=new HashSet<>();
        hashSet1.add("广州");
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2=new HashSet<>();
        hashSet2.add("成都");
        hashSet2.add("杭州");

        HashSet<String> hashSet3=new HashSet<>();
        hashSet3.add("上海");
        hashSet3.add("天津");

        HashSet<String> hashSet4=new HashSet<>();
        hashSet4.add("广州");
        hashSet4.add("杭州");
        hashSet4.add("大连");

        hashMap.put("k1",hashSet);
        hashMap.put("k2",hashSet1);
        hashMap.put("k3",hashSet2);
        hashMap.put("k4",hashSet3);
        hashMap.put("k5",hashSet4);

        HashSet<String> allAreas=new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");


        HashSet<String> select=new HashSet<>();

        HashSet<String> tempAreas=new HashSet<>();

        String maxkey=null;

        while (allAreas.size()!=0){
            maxkey=null;
            for (String key:hashMap.keySet()) {
                tempAreas.clear();//每次都要清空集合
                HashSet<String> areas=hashMap.get(key);//获取key对应的集合
                tempAreas.addAll(areas);
                tempAreas.retainAll(allAreas);//获取对应的交集
                if (tempAreas.size()>0&&(maxkey==null||tempAreas.size()>hashMap.get(maxkey).size())){//如果当前这个集合包含未覆盖地区的数量比maxKey指向的集合包含未覆盖地区的数量还多就需要重置maxKey和它指向的集合包含未覆盖地区集合

                    maxkey=key;
                }
                if (maxkey!=null){
                    select.add(maxkey);//获取覆盖区域的String
                    allAreas.removeAll(hashMap.get(maxkey));//删去已经完成覆盖的
                }
            }

        }
        System.out.println(select);
    }
}
